package sort.insert;

import sort.SortArr;

import java.util.Arrays;

/**
 * @ Project: JavaSort
 * @ Package: sort.insert
 * @ Title 标题（要求能简洁地表达出类的功能和职责）
 * @ Description: 描述（简要描述类的职责、实现方式、使用注意事项等）
 * @ author : qw
 * @ CreateDate: 2020/12/21 11:22
 * @ Version: 1.0
 * @ Copyright: Copyright (c) 2020
 * @ History: 修订历史（历次修订内容、修订人、修订时间等）
 */
public class DirectInsertionSort {
    /**
     * 直接插入排序
     * 时间复杂度 O(N2)
     * 空间复杂度 O(1)
     * 稳定且简单
     */
    public static void directInsertion() {
        int[] arr = Arrays.copyOf(SortArr.sortArr,SortArr.sortArr.length);
        System.out.println("直接插入排序前的数组");
        System.out.println(Arrays.toString(arr));

        for (int i = 1 ;i < arr.length;i++) {
            int temp = arr[i];
            int j;
            for (j = i-1;j >= 0; j--) {
                // 升序
                if (arr[j] > temp) {
                    arr[j+1] = arr[j];
                }else {
                    break;
                }
            }
            arr[j+1] = temp;
        }
        System.out.println("直接插入排序后的数组");
        System.out.println(Arrays.toString(arr));
    }
}
